<?php
$this->breadcrumbs=array(
	'sudoku'=>array('sudoku'),
	'sudoku',
);?>

<script type="text/javascript">
            $(document).ready(
                    function(){
                        $(window).load(
                             function(){
                                 var counter = 0;
                                 var inputSet = $("#sdtable input");
                                 $("#sdtable input").each(
                                 function(){
                                 this.id = ""+counter;
                                 counter++;
                                 this.maxLength="1";
                                 this.onblur=function(){
                                    validate(this);
                                 }
                                   }
                                );
                             }
                        );
                    }
                    );
            function examineNum(item){
                if(isNaN(item.value)){
                    alert("Please input a number!");
                    item.value = "";
                }
            }
        </script>
        <style type="text/css">
            #sdtable tr{
                margin: 0px;
            }
            #sdtable tr td{
                margin: 0px;
                padding: 0px;
            }
            #sdtable input {
                width: 30px;
                height: 30px;
                margin: 0px;
                padding: 0px;
                text-align: center;
                font-family:Verdana, Geneva, sans-serif;
                font-size: 20px;
                border: none;
            }
            #sdtable table {
                margin: 0px;
                padding: 0px;
            }
            #sdtable {
                border-spacing: 0px;
            }
            #sdtable table{
                border-spacing: 0px;
                border: 2px solid #666;
            }
        </style>
        <script type="text/javascript">
//To generate the Matrix of Sudoku
//<![CDATA[

/***
	
		产生一个 9*9 的数独矩阵，满足数独规则 :
		
		1.一个由9个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，
		
		2.且数独矩阵中每行每列都没有重复数字。
		
		
		关键方法：
		深度搜索，记下每个单元格对应的可选数序列，当没有路线时清空自己的可选数序列,
		利用回朔，改变上个单元格已选泽的值
		
		
	
	
	****/	
	if(!Array.prototype.indexOf) {  
	   Array.prototype.indexOf = function(v){  
	        for(var i=0;i<this.length;i++)  
	            if(this[i] === v) return i;  
	        return -1;  
	    }  
	}  
//http://blog.stevenlevithan.com/archives/faster-trim-javascript
//fast !
	if(!String.prototype.trim) { 
			String.prototype.trim=function() {
	                      var	str = this.replace(/^\s\s*/, ''),
		              ws = /\s/,
		               i = str.length;
	                       while (ws.test(str.charAt(--i)));
	                       return str.slice(0, i + 1);
                          }
	}
	
	
       
	/*
		*********************************************************************
		start : 数组随机函数组
	
		floy 算法对数组进行重排序
		http://yiminghe.iteye.com/blog/409039
	*/

  function randIt(l,u){  
       return l+Math.floor(Math.random()*(u-l+1));  
  }
  
  
  /* 
       1 - n 中随机取m个数组成序列 
   */  
   function randomList(m,n) {  
       var start=n-m+1;  
       var holder=[];  
         
       for(var i=start;i<=n;i++) {  
           //random 1~i not 1~i-1  
           var cur=randIt(1,i);  
           //trick tick  
           var position=holder.indexOf(cur)+1;       
           var insert=position?i:cur;  
           holder.splice(position,0,insert);                 
       }  
         
       return holder;  
    }
   
   
   /**
   	arr 数组元素随机打乱
   **/
   function randomArray(arr) {
  		var rIndex=randomList(arr.length,arr.length);
  		var newArr=[];
  		for(var i=0;i<rIndex.length;i++) {
  			newArr[i]=arr[rIndex[i]-1];
  		}
  		return newArr;
  		
   }
   
/*
	end : 数组随机函数组
	********************************************************************************
*/   
   
   
 
	/*
		数独 core 对象 ,其实就是对2维数组的封装
	*/ 
	function Sudoku(){	
	
	}  


   
       

	/*
		得到当前单元格的一个可选值，-1 表示没有可选值了，要向前回朔
	*/
	Sudoku.prototype.getNextRandom = function(currentCell){		
		
		var currentX=currentCell%9; //col
		var currentY=Math.floor(currentCell/9); //row
		var currentSubMaxtrixX=Math.floor(currentX/3); //sub this.matrix col
		var currentSubMaxtrixY=Math.floor(currentY/3); //sub this.matrix row
		var index=0;
		
		//初始可选数字
		var avails=[1,2,3,4,5,6,7,8,9];		
		
		//没有计算过，计算可选序列，用于回朔枚举
		if(!this.matrix[currentY][currentX]) {			
			
			/*
				根据数独规则进行过滤
			*/
			
			//同一行不能重复
			for(var i=0;i<currentX;i++) {
				if(avails.indexOf(this.matrix[currentY][i].value)!=-1)
					avails.splice(avails.indexOf(this.matrix[currentY][i].value),1);
			}
			
			//同一列不能重复
			for(var i=0;i<currentY;i++) {
				if(avails.indexOf(this.matrix[i][currentX].value)!=-1)
					avails.splice(avails.indexOf(this.matrix[i][currentX].value),1);
			}
			
			//3*3 小矩阵不能重复
			outer:for(var j=currentSubMaxtrixY*3;j<currentSubMaxtrixY*3+3;j++) {		
				for(var i=currentSubMaxtrixX*3;i<currentSubMaxtrixX*3+3;i++) {
					
					//小矩阵验证到当前单元格就行了
					if(j==currentY && i==currentX) break outer;			
					
					if(avails.indexOf(this.matrix[j][i].value)!=-1)
						avails.splice(avails.indexOf(this.matrix[j][i].value),1);
				}
			}
			
			//没有选择了
			if(avails.length==0) return  -1;
			
			//avails 最好随机打乱，每次生成不同的数独
			avails=randomArray(avails);
			
		} else {
			
			index=this.matrix[currentY][currentX].index;
			
			//枚举完毕，仍然不行，清除计算状态，
			if(index == this.matrix[currentY][currentX].availList.length-1) {
				this.matrix[currentY][currentX]=null;
				return -1;
			}
			
			//回朔到这里了，当前数字不行，那么在可选序列中选中下一个可选数字
			++index;
			avails=this.matrix[currentY][currentX].availList;
				
		}
		
		//返回数独单元的结构表示
		return {
			//当前单元格选择的值的index
			index:index,
			//记下产生的可选序列，回朔时用于枚举下一个值
			availList:avails,
			value:avails[index]
		};
		
	}
	
	
	/*
		指定编号的 Cell 设置数值
	*/
	Sudoku.prototype.setValueOfMatrix = function(currentCell,val) {
		var currentX=Math.floor(currentCell%9); //col
		var currentY=Math.floor(currentCell/9); //row
		this.matrix[currentY][currentX]=val;
	}
	
	
	/*
		静态方法：验证是否符合数独规则
	*/
	Sudoku.validate = function (matrix){
		var cache={};
		
		for(var i=0;i<9;i++) {
			cache={};
			for(var j=0;j<9;j++) {
				if(cache[matrix[i][j]]) {
					
					return "row "+(i+1)+"  error";	
				}		
				cache[matrix[i][j]] = 1;
			}
		}	
		
		
		for(var i=0;i<9;i++) {
			cache={};
			for(var j=0;j<9;j++) {
				if(cache[matrix[j][i]]) {
					
					return "col "+(j+1)+"  error";
				}	
				cache[matrix[j][i]] = 1;
			}
		}	
		
		
		for(var i=0;i<3;i++) {
			
			for(var j=0;j<3;j++) {
				
				cache={};
				
				for(var subi=i*3;subi<i*3+3;subi++) {
					
					for(var subj=j*3;subj<j*3+3;subj++) {
						
						if(cache[[matrix[subi][subj]]]) {
							
							return "submatrix "+(i*3+j)+"error";
						}
						cache[matrix[subi][subj]] = 1;
				
					}	
					
				
				}	
					
			}
		}	
		return null;		
	}
	
	
	/*
		重要，生成符合数独规则的矩阵
	*/
	Sudoku.prototype.generate = function (space) {
		this.matrix=[];
		
		for(var i=0;i<9;i++) 
			this.matrix.push([]);			
		
		var currentCell=0;
		
		//按照行编号 0~80 ,共 9*9=81 个单元格
		while(true) {
			var nextValue=this.getNextRandom(currentCell);			
			if(nextValue!=-1) {
				this.setValueOfMatrix(currentCell,nextValue);
				++currentCell;
			} else {
				//无值可选了，回朔
				--currentCell;	
			}
			
			//9*9 全部完成
			if(currentCell==81) break;
		}
		
		
		
		/*
			矩阵已经搞好了--------------------------------------------
		*/ 
					
		var holes=randomList(space,81);
		
		for(var i=0;i<holes.length;i++) {
			var currentX=Math.floor((holes[i]-1)%9); //col
			var currentY=Math.floor((holes[i]-1)/9); //row
			this.matrix[currentY][currentX]=null;
		}
		
		return this.matrix;		
		
	}
//]]>
</script>
<script type="text/javascript">
    /*
    add hit function to array
    */
    Array.prototype.hitIndex = function (elem) {
        var hitArray = new Array();
        for (var i = 0; i < this.length; i++) {
            if (this[i] == elem) {
                hitArray.push(i);
            }
        }
        return hitArray;
    }

    /* =====================================*/

    var sudoku = new Sudoku();
    var space;
    $(document).ready(
            function(){
                $("#generate").click(
                    function(){
                    //get space
                    var spaceStr = document.getElementById("space").value;
                    space = parseInt(spaceStr);
                    if(isNaN(space)){
                        alert("Please input a number!")
                        return;
                    }
			
			        if(space>16 || space<0) {
			        	alert("Please input the number between 1 and 15:(");
			        	return;
		        	}
                    var matrix= sudoku.generate(space);
                    var inputList = $(".lat");
                    //clear job
                    for(var k=0;k<81;k++){
                        inputList[k].value = "";
                        inputList[k].readOnly = "";
                        $(inputList[k]).css("background-color","#fff");
                    }
                    for(var i=0;i<9;i++){
                    for(var j=0;j<9;j++){
                    var index = (Math.floor(i/3))*27+(Math.floor(j/3))*9+(i%3)*3+j%3;
                    if(matrix[i][j]){
                        inputList[index].value = matrix[i][j].value;
                        inputList[index].readOnly = "true";
                        $(inputList[index]).css("background-color","#eee");
                    }
                    }
                    }
                    }
                        );
                    }
                    );
    $(document).ready(
            function(){
                $("#validate").click(
                    function(){
                        var valid = true;
                        var outputMatrix = $(".lat");
                        var Matrix = new Array();
                        for(var i=0;i<81;i++){
                            Matrix.push(outputMatrix[i].value);
                        }
                        for(var i=0;i<9;i++){//i is the i th sub-square
                            /* form a subArray */
                            var subArray = new Array();
                            for(var k=0;k<9;k++){
                                subArray.push(Matrix[i*9+k]);
                            }
                            for(var j=0;j<9;j++){
                                if(subArray.count(Matrix[i*9+j])>=2){
                                    valid = false;
                                }
                            }
                        }
                        var bigMatrix = new Array();
                        for(var i=0;i<9;i++){
                            for(var j=0;j<9;j++){
                                var index = (Math.floor(i/3))*27+(Math.floor(j/3))*9+(i%3)*3+j%3;
                                bigMatrix.push(Matrix[index]);
                            }
                        }
                        /* Check line */
                        for (var i=0;i<9;i++){
                            /* form line array */
                            var lineArray = new Array();
                            for(var j=0;j<9;j++){
                                lineArray.push(bigMatrix[i*9+j]);
                            }
                            for(var k=0;k<9;k++){
                                if(lineArray.count(bigMatrix[i*9+k])>=2){
                                    valid = false;
                                }
                            }
                        }
                        /* Check col */
                        for (var i=0;i<9;i++){
                            /* form col array */
                            var lineArray = new Array();
                            for(var j=0;j<9;j++){
                                lineArray.push(bigMatrix[j*9+i]);
                            }
                            for(var k=0;k<9;k++){
                                if(lineArray.count(bigMatrix[k*9+i])>=2){
                                    valid = false;
                                }
                            }
                        }
                        if (valid){
                            alert("Congratulations, You've made it!!");
                        }
                        else {
                            alert("I'm sorry, it's in correct, Please try again <3");
                        }
                    }
                );
                
            }
    );

        /* Validation function,
        Be invoke after the input text is blured.
        */
        function validate(input){
            if (input.value!=""){
            // examine is a num ?
            if(isNaN(input.value)){
                    alert("Please input a number!");
                    input.value = "";
            }
            var clear = true;
            var Matrix = $(".lat");
            var id = parseInt(input.id);
            var gridIndex = Math.floor(id/9);
            var gridOff = id % 9;
            // form grid array, the elem in grid array is input text!!
            var gridArray = new Array();
            for(var i=0;i<9;i++){
                gridArray.push(Matrix[gridIndex*9+i]);
            }
            //muteHit(gridArray,input);
            if(muteHit(gridArray,input)==false){
                clear = false;
            }
            // ------------------------------------------------------------
            var bigMatrix = new Array();
            for(var i=0;i<9;i++){
                for(var j=0;j<9;j++){
                    var index = (Math.floor(i/3))*27+(Math.floor(j/3))*9+(i%3)*3+j%3;
                    bigMatrix.push(Matrix[index]);
                }
            }
            var ith = Math.floor(id/27)*3 + Math.floor((id%9)/3);
            var jth = Math.floor(id/9)%3*3+ id%3;
            //alert("i:"+i+" j:"+j);
            // form line array
            var lineArray = new Array();
            for(var i=0;i<9;i++){
                lineArray.push(bigMatrix[ith*9+i]);
            }
            //muteHit(lineArray,input);
            if(muteHit(lineArray,input)==false){
                clear = false;
            }
            //form colum array
            var colArray = new Array();
            for(var i=0;i<9;i++){
                colArray.push(bigMatrix[i*9+jth]);
            }
            //muteHit(colArray,input);
            if(muteHit(colArray,input)==false){
                clear = false;
            }
            if (clear == false){
                input.value = "";
            }
            else{
                checkWin(Matrix);
            }
            /*
            //alert(input.value);
            var outputMatrix = $(".lat");
            var Matrix = new Array();
            //Matrix in 3*3*9 order.
            for(var i=0;i<81;i++){
                Matrix.push(outputMatrix[i].value);
            }
            var id = parseInt(input.id);
            var sIndex = Math.floor(id/9); 
            var subArray = new Array();
            for(var k=0;k<9;k++){
                subArray.push(Matrix[sIndex*9+k]);
            }
            var j = id % 9 ;
            var hitArray = subArray.hitIndex(Matrix[id]);
            var i;
            for (i in hitArray){
                if (hitArray[i] != j)
                    muteColor(outputMatrix[sIndex*9+hitArray[i]]);
                outputMatrix[id].value = "";
            } 

            */
        }
        }
        function checkWin(Matrix){
            var win = true;
            for (var i = 0; i < 81; i++) {
                if (Matrix[i].value==""){
                    win = false;
                }
            };
            if(win==true){
                alert("Congratulations!!You've got it!! <3");
            }
        }
        function muteHit(targetArray,input){
            var hitArray = hit(targetArray,input);
            for (var i=0; i<hitArray.length;i++){
                muteColor(hitArray[i]);
            }
            if(hitArray.length>0){
                return false;
            }
            else{
                return true;
            }
        }
        /*
         ** param: inputArray(to be tested) input(target elem)
         ** ret  : the input elems that duplicate;
         */
        function hit(inputArray,input){
            var hitArray = new Array();
            for (var i = 0; i < inputArray.length; i++) {
                if ((inputArray[i].value == input.value)&&(inputArray[i].id != input.id)) {
                    hitArray.push(inputArray[i]);
                };
            };
            return hitArray;
        }

       function muteColor(input){
            $(document).ready(function() {
                $(input).animate({"fontSize":"25px"},"slow");
                $(input).animate({"fontSize":"20px"},"slow");
            });
            /*
            $(function(){
                $(input).bind("tranColor",
                    function(){
                        this.animate({background-color:"red"},"slow");
                    }
                );
                $(input).trigger("tranColor");
                //$(input).animate({background-color:expression(bgColor+"")},"slow");
                }
            );
            */
        }
</script>
<div class = "row">
	<div class="span3 offset4">
        <table id = "sdtable">
            <tr>
                <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
</tr>
<tr>
                <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
</tr>
<tr>
                <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
    <td>
        <table border="1" style="border-collapse: collapse">
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
            <tr>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
                <td><input type="text" class="lat"/></td>
            </tr>
        </table>
    </td>
</tr>
</table>
<button class="btn btn-primary" id = "generate">Generate</button> 
<button class="btn btn-danger" id = "validate">Validate</button>
<form style="margin-top:10px;">
    Space:
    <input type="text" id ="space"/>
</form>
</div>
</div>